package com.carl.leetcode.pointer;

/**
 * Created by carlXie on 2016/3/13.
 */
public class LinkedList {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            this. val = x;
        }
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null)
            return null;

        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        if(fast == null) {
            head = head.next;
            return head;
        }

        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return head;
    }

    public static ListNode swapPairs(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;

        // 交换后在前面的节点，即原来在后面的节点
        ListNode front = head.next;
        // 交换后在后面的节点，即原来在前面的节点
        ListNode behind = head;
        head = front;
        // 后面的节点以后的节点，即去除前两个节点后剩余的节点
        ListNode rest = front.next;

        while(front != null && behind != null) {
            front.next = behind;
            behind.next = rest;

            if(rest != null && rest.next != null) {
                behind.next = rest.next;
                front = rest.next;
                behind = rest;
                rest = front.next;
            } else {
                break;
            }
        }

        return head;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || k == 1) return head;

        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head;

        ListNode currentHead = fakeHead;
        ListNode next = head;

        int i = 0;
        while(next != null) {
            ++ i;
            if(i % k == 0) {
                currentHead = reverse(currentHead, next);
                next = currentHead.next;
            } else {
                next = next.next;
            }
        }

        return fakeHead.next;
    }

    /**
     * 反转front后一个节点到tail之间的节点，例如：
     * front              tail
     * |                   |
     * 1 -> 2 -> 3 -> 4 -> 5
     *
     * 反转后变成：
     * 1 -> 5 -> 4 -> 3 -> 2
     *
     * @param front
     * @param tail
     * @return 该链表的最后一个节点
     */
    private static ListNode reverse(ListNode front, ListNode tail) {
        ListNode last = front.next;
        ListNode cur = last.next;

        while(cur != tail) {
            last.next = cur.next;
            cur.next = front.next;
            front.next = cur;
            cur = last.next;
        }

        last.next = tail.next;
        tail.next = front.next;
        front.next = tail;

        return last;
    }

    public static void main(String[] args) {

        ListNode head = new ListNode(1);
        ListNode current = head;

        for (int i = 2; i < 7; i++) {
            current.next = new ListNode(i);
            current = current.next;
        }

        head = reverseKGroup(head, 2);

        // removeNthFromEnd(head, 2);
        // head = swapPairs(head);

        while(head.next != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.println(head.val);
    }
}
